#include <iostream>
#include <jni.h>
#include "com_hgd_jni_Cluster.h"
#include <math.h>

using namespace std;

#define N 100
#define K 12
#define r 8
#define LOOP 10000

//int E1[2000][1000] = {{3, 20, 8, 9, },       {5, 2, 14, 14, },       {4, 9, 12, 13, },       {8, 4, 13, 3, },       {11, 18, 18, 6, }, 
//{11, 17, 8, 6, },       {4, 16, 6, 12, },       {14, 15, 1, 11, },       {9, 11, 3, 5, },       {11, 9, 13, 11, },   
//{14, 12, 5, 19, },       {2, 20, 7, 16, },       {2, 3, 20, 15, },       {19, 4, 17, 2, },       {11, 9, 9, 1, },     
//{11, 7, 17, 12, },       {13, 8, 11, 20, },       {8, 13, 15, 7, },       {20, 12, 18, 15, },       {13, 12, 7, 11,}};

//int E[2000][2000] = {{4, 17, 19, 9, 16, 19, 12, 1, 5, 12, 16, 4, },       {20, 14, 18, 5, 2, 5, 4, 15, 11, 7, 4, 14, },       {20, 9, 16, 4, 8, 20, 12, 19, 1, 14, 1, 3, },       {12, 1, 8, 10, 12, 15, 20, 10, 11, 3, 20, 17, },       {17, 20, 4, 7, 3, 12, 17, 17, 13, 13, 5, 19, },       {4, 3, 3, 12, 10, 13, 6, 14, 16, 16, 6, 7, },       {9, 3, 17, 11, 18, 19, 16, 10, 5, 3, 8, 3, },       {2, 8, 20, 16, 14, 1, 10, 12, 7, 15, 3, 12, },       {18, 18, 12, 12, 2, 11, 9, 6, 20, 6, 12, 15, },       {3, 2, 9, 18, 12, 6, 14, 15, 2, 15, 1, 10, },       {13, 1, 6, 1, 10, 18, 11, 7, 8, 2, 18, 8, },       {7, 17, 13, 10, 4, 12, 12, 7, 13, 15, 13, 2, },       {18, 9, 3, 10, 7, 13, 2, 4, 19, 16, 10, 2, },       {14, 17, 17, 11, 18, 16, 3, 8, 15, 7, 2, 8, },       {16, 20, 4, 13, 2, 6, 15, 11, 20, 7, 14, 14, },       {1, 7, 12, 14, 15, 3, 19, 6, 5, 20, 2, 8, },       {4, 1, 8, 16, 17, 18, 11, 18, 8, 2, 14, 13, },       {6, 3, 9, 3, 10, 10, 6, 12, 18, 7, 12, 20, },       {18, 11, 12, 7, 13, 18, 16, 10, 14, 10, 12, 17, },       {7, 8, 8, 6, 6, 4, 13, 9, 11, 19, 2, 3, },       {17, 18, 2, 5, 15, 2, 13, 12, 4, 1, 7, 11, },       {16, 6, 1, 17, 16, 14, 17, 12, 6, 20, 9, 7, },       {12, 5, 7, 18, 6, 12, 12, 6, 3, 6, 1, 15, },       {16, 7, 19, 11, 3, 9, 2, 9, 15, 2, 10, 15, },       {11, 11, 5, 20, 20, 1, 2, 3, 3, 17, 8, 18, },       {6, 19, 5, 14, 8, 1, 7, 19, 10, 20, 2, 1, },       {19, 4, 19, 4, 20, 5, 6, 3, 14, 18, 19, 19, },       {2, 20, 4, 4, 13, 3, 4, 4, 12, 3, 20, 16, },       {7, 4, 2, 15, 12, 1, 5, 17, 15, 6, 17, 1, },       {3, 20, 2, 3, 19, 20, 20, 4, 8, 8, 5, 10, },       {12, 4, 7, 7, 11, 9, 7, 11, 9, 9, 10, 18, },       {2, 13, 2, 2, 6, 11, 16, 1, 5, 13, 2, 8, },       {14, 19, 14, 10, 3, 20, 3, 7, 3, 9, 8, 18, },       {15, 6, 4, 4, 2, 3, 14, 20, 7, 4, 18, 8, },       {6, 7, 20, 5, 10, 16, 2, 18, 3, 7, 3, 9, },       {15, 15, 10, 9, 7, 4, 19, 8, 2, 6, 2, 12, },       {6, 7, 19, 12, 19, 3, 9, 13, 1, 13, 10, 11, },       {8, 20, 7, 2, 5, 12, 15, 11, 19, 15, 5, 1, },       {19, 5, 13, 3, 15, 2, 1, 15, 18, 12, 11, 4, },       {14, 3, 20, 3, 17, 5, 10, 15, 17, 2, 13, 16, },       {16, 14, 12, 4, 14, 4, 19, 14, 12, 3, 2, 8, },       {3, 14, 14, 5, 13, 7, 15, 3, 15, 1, 7, 16, },       {12, 9, 1, 11, 17, 2, 7, 5, 5, 5, 3, 15, },       {7, 10, 16, 5, 11, 2, 1, 7, 2, 1, 2, 1, },       {18, 10, 18, 15, 11, 16, 20, 12, 1, 6, 10, 12, },       {17, 2, 6, 3, 20, 12, 14, 7, 9, 2, 7, 4, },       {1, 19, 4, 1, 10, 9, 17, 9, 16, 13, 7, 3, },       {17, 9, 14, 5, 15, 9, 20, 9, 9, 8, 17, 10, },       {2, 13, 12, 4, 17, 17, 15, 5, 19, 3, 7, 11, },       {14, 4, 4, 6, 9, 4, 10, 8, 12, 8, 18, 14, },       {19, 5, 18, 10, 12, 8, 1, 15, 8, 1, 6, 7, },       {14, 10, 15, 12, 19, 19, 4, 14, 7, 17, 15, 12, },       {12, 20, 15, 12, 1, 19, 12, 7, 16, 13, 8, 2, },       {11, 15, 6, 15, 13, 1, 3, 14, 7, 2, 10, 18, },       {11, 1, 13, 5, 4, 20, 17, 2, 15, 13, 11, 11, },       {16, 16, 6, 19, 3, 6, 18, 10, 16, 4, 11, 17, },       {4, 12, 14, 3, 11, 15, 15, 1, 1, 20, 10, 19, },       {8, 12, 3, 12, 5, 9, 8, 2, 13, 12, 19, 14, },       {14, 10, 15, 17, 1, 12, 8, 12, 7, 6, 8, 9, },       {6, 17, 17, 10, 8, 17, 13, 9, 9, 11, 19, 13,}};


int X[1000] = {-1};

int P[1000] = {-1};
int Pnum = 0;

int PX[1000] = {-1};
int PXnum = 0;

int XX[1000] = {-1};
int Xnum = 0;

int device[1000];
int domain[1000];
int center[1000];
int Cnum;
int dnum = 0;

int TempE[2000][1000] = {0};
int Max = 0;
int Min = 0;
int Maxnum = 0;
int Minnum = 0;
int changeno = 0;

int G_TempE[2000][1000] = {0};

int Change_Center(int c)
{
	int sum = 0;
	int num = 0;

	for (int i = 0; i < N; i++)
	{
		if (domain[i] == c)
		{
			sum += device[i];
			num++;
		}
	}

	c = (int)(sum/num);

	return c;
}

void Cluster(int E[100][12])
{
	int temp;
	for (int i = 0; i < N; i++)
	{
		temp = E[i][0];
		for (int j = 1; j < K; j++)
		{
			if (E[i][j] < temp)
			{
				temp = E[i][j];
			}
		}
		device[i] = temp;

		domain[i] = -1;
	}
	
	int flag = 0;
	center[0] = device[0];
	Cnum = 1;
	domain[0] = 0;
	for (int i = 1; i < N; i++)
	{
		flag = 0;
		for (int j =0; j < Cnum; j++)
		{
			if (device[i]-center[j] < r)
			{
				domain[i] = j;
				center[j] = Change_Center(j);
				flag = 1;
				break;
			}
		}
		if (flag == 0)
		{
			center[Cnum] = device[i];
			domain[i] = Cnum;
			Cnum++;
		}
	}
}

void FindMaxMin()
{
	int SUM = 0;

	Max = -1;
	Min = 10000;
	Maxnum = -1;
	Minnum = -1;

	for (int j = 0; j < K; j++)
	{
		SUM = 0;
		for (int i = 0; i < dnum; i++)
		{
			if (X[i] == j)
			{
				SUM += TempE[i][j];
			}
		}

		if (SUM > Max)
		{
			Max = SUM;
			Maxnum = j;
		}
		if (SUM < Min)
		{
			Min = SUM;
			Minnum = j;
		}
	}
}

void FindDomainMin()
{
	int minvalue = 1000;
	int cost = 0;

	for (int i = 0; i < dnum; i++)
	{
		if (X[i] == Maxnum)
		{
			cost = TempE[i][Minnum] - TempE[i][Maxnum];
			if (minvalue > cost)
			{
				minvalue = cost;
				changeno = i;
			}
		}
	}
}

void G_FindMaxMin()
{
	int SUM = 0;

	Max = -1;
	Min = 10000;
	Maxnum = -1;
	Minnum = -1;

	for (int j = 0; j < K; j++)
	{
		SUM = 0;
		for (int i = 0; i < Pnum; i++)
		{
			if (P[i] == j)
			{
				SUM += G_TempE[i][j];
			}
		}

		if (SUM > Max)
		{
			Max = SUM;
			Maxnum = j;
		}
		if (SUM < Min)
		{
			Min = SUM;
			Minnum = j;
		}
	}
}

void G_FindDomainMin()
{
	int minvalue = 10000;
	int cost = 0;

	for (int i = 0; i < Pnum; i++)
	{
		if (P[i] == Maxnum)
		{
			cost = G_TempE[i][Minnum] - G_TempE[i][Maxnum];

			if (minvalue > cost)
			{
				minvalue = cost;
				changeno = i;
			}
		}
	} //閫夋嫨鏈�皬鐨勬墽琛屾椂闂�
}

void PPartition()
{
	int tmin = 0;
	int tno = 0;
	int loop = 0;

	for (int i = 0; i < dnum; i++)
	{
		tmin = TempE[i][0];
		tno = 0;
		for (int j = 1; j < K; j++)
		{
			if (TempE[i][j] < tmin)
			{
				tmin = TempE[i][j];
				tno = j;
			}
		}
		X[i] = tno;
		//cout << "X[i] = "  << X[i]  << "      " << endl;
	}  //鏈�皬鍊煎姞鍏�

	loop = 0;
	int fit = 0;
	int best = 10000;

	//鎵惧嚭鏈�ぇ鏈�皬璐熻浇
	FindMaxMin();
	best = Max -Min;
	while(loop < LOOP)
	{
		//鎵惧嚭鏈�ぇ鍩熶腑鏈�皬鍊�
		FindDomainMin();

		//鏈�皬鍊煎姞鍏ュ埌鏈�ぇ鍊�
		X[changeno] = Minnum;
		//鎵惧嚭鏈�ぇ鏈�皬璐熻浇
		FindMaxMin();
		fit = Max -Min;
		if (fit < best)
		{
			best = fit;

			for (int i = 0; i < dnum; i++)
			{
				PX[i] = X[i];
			}
			PXnum = dnum;
			//涓嶆敼鍙�
			//X[changeno] = Maxnum;
		}

		loop++;
	}

	cout << "fitness=" << best << endl;

	int j = Pnum;
	for (int i = 0; i < dnum; i++)
	{
		P[j] = PX[i];
		j++;
	}
	Pnum += dnum;

	loop = 0;
	int G_best = 10000;

	//鎵惧嚭鏈�ぇ鏈�皬璐熻浇
	G_FindMaxMin();
	G_best = Max -Min;
	while(loop < LOOP)
	{
		//鎵惧嚭鏈�ぇ鍩熶腑鏈�皬鍊�
		G_FindDomainMin();

		//鏈�皬鍊煎姞鍏ュ埌鏈�ぇ鍊�
		P[changeno] = Minnum;
		//鎵惧嚭鏈�ぇ鏈�皬璐熻浇
		G_FindMaxMin();

		fit = Max -Min;
		if (fit < G_best)
		{
			G_best = fit;

			for (int i = 0; i < Pnum; i++)
			{
				XX[i] = P[i];
			}
			Pnum = Xnum;
			//涓嶆敼鍙�
			//P[changeno] = Maxnum;
		}

		loop++;
	}
	cout << "G_fitness=" << G_best << endl;
}	

void Partition(int E[100][12])
{

	for (int t = 0; t < Cnum; t++)
	{
		dnum = 0;
		int pptempnum = Pnum;
		for(int i = 0; i < N; i++)
		{
			if (domain[i] == t)
			{
				for (int j = 0; j < K; j++)
				{
					TempE[dnum][j] = E[i][j];
					G_TempE[pptempnum][j] = E[i][j];
				}
				dnum++;
				pptempnum++;
			}
		}
		PPartition();
	}
}

double fitness(int PP[2000],int E[100][12])
{
	double sum = 0;
	double ave = 0.0;
	double SUM = 0.0;
	double D[2000] = {0};  //鍩熺殑璐熻浇

	sum = 0;
	for (int j = 0; j < K; j++)
	{
		D[j] = 0;
		for (int i =0; i < N; i++)
		{
			if (PP[i] == j)
			{
				D[j] += E[i][j];
			}
		}
		sum +=  D[j];
		  
		cout << "D[J]=" << D[j] << endl;
	}

	ave = (double)(sum/K);
	
	for (int j = 0; j < K; j++)
	{
		SUM += pow((double)(D[j] - ave), 2);
	}
	return sqrt(SUM/K);
}

JNIEXPORT jintArray JNICALL Java_com_hgd_jni_Cluster_getTwoArray(JNIEnv *env,jobject obj,jobjectArray array,jint JN, jint JK){
	
	jint i,j;
	int E[100][12];
	jarray myarray;
	int size = env->GetArrayLength(array);
	for(i = 0;i<size;i++)
	{
		myarray = (jarray)env->GetObjectArrayElement(array, i);
		int col = env->GetArrayLength(myarray);
		
		jint *coldata = env->GetIntArrayElements((jintArray)myarray, 0);
		for (j=0; j<col; j++) 
       {
           E[i][j] = coldata[j];
           //printf("number:%dn",E[i][j]);
       }
       env->ReleaseIntArrayElements((jintArray)myarray, coldata,0 );
	}
	
	Cluster(E);
	
	Partition(E);
	
	for (int i = 0; i < N; i++)
	{
		cout << P[i] << "    " << endl; 
	}

	cout << "Max=" << Max << "   Maxnum=" << Maxnum << "   Min=" << Min << "   Minnum=" << Minnum << endl;
	cout << "fitness=" << fitness(P,E) << endl;
	jint *jP = (jint*)P; 
	jintArray p = env->NewIntArray(JN);
	env->SetIntArrayRegion(p,0,JN,jP);
	//system("pause");
	
	return p;
}

